package com.sedric.sort;

import java.util.ArrayList;
import java.util.List;

public class QuickSort {

	public static void quickSort(List<Integer> nodes, int start, int end) {
		if (start < end) {
			Integer base = nodes.get(start);

			int i = start;

			int j = end + 1;

			while (true) {
				while (i < end && nodes.get(++i) >= base)
					;
				System.out.println(nodes.get(i));
				while (j > start && nodes.get(--j) <= base)
					;

				System.out.println(nodes.get(j));
				if (i < j) {
					swap(nodes, i, j);
				} else {
					break;
				}
			}
			swap(nodes, start, j);
			quickSort(nodes, start, j - 1);
			quickSort(nodes, j + 1, end);
		}
	}

	private static void swap(List<Integer> nodes, int i, int j) {
		Integer tmp;
		tmp = nodes.get(i);
		nodes.set(i, nodes.get(j));
		nodes.set(j, tmp);
	}

	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		list.add(3);
		list.add(1);
		list.add(6);
		list.add(2);
		list.add(8);
		list.add(9);
		list.add(4);

		quickSort(list, 0, list.size() - 1);

		for(Integer i : list) {
			System.out.println(i);
		}
	}
}
